首页 > 试题广场 >

二分查找-II

[编程题]二分查找-II
  • 热度指数：189145 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请实现有重复数字的升序数组的二分查找
给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

数据范围：
进阶：时间复杂度，空间复杂度
示例1

输入

[1,2,4,4,5],4

输出

2

说明

从左到右，查找到第1个为4的，下标为2，返回2
示例2

输入

[1,2,4,4,5],3

输出

-1
示例3

输入

[1,1,1,1,1],1

输出

0
算法知识视频讲解
添加回答
Python 3
Q4头像 Q4 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        lo,hi = 0, len(nums)-1 
        while lo <= hi:
            mid = lo + (hi-lo) //2 
            if nums[mid] == target:
                while mid != 0 and nums[mid-1] == nums[mid]:
                    mid -= 1
                return mid 
            elif nums[mid] > target:
                hi = mid -1 
            else:
                lo = mid +1 
        return -1 

发表于 2022-05-24 13:55:17 回复(0)
Python 3
azedplayer头像 azedplayer
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        return nums.index(target) if target in nums else -1
发表于 2022-05-09 23:17:13 回复(0)
Python 3
danspace头像 danspace 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        l, r = 0, len(nums)-1
        while l <= r:
            i = (l+r)//2
            while target == nums[i]:                
                if i -1 < 0&nbs***bsp;target != nums[i-1]:
                    return i
                else:
                    i -= 1
            if target > nums[i]:
                l = i+1
            elif target < nums[i]:
                r = i-1
        return -1

发表于 2022-04-25 10:42:05 回复(0)
Python 3
牛客318213606号头像 牛客318213606号 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        n=len(nums)
        left,right=0,n-1
        res=-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                res=mid
                right=mid-1
            elif nums[mid]>target:
                right=mid-1
            elif nums[mid]<target:
                left=mid+1
        return res

发表于 2022-02-08 13:59:51 回复(0)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        if not nums:
            return -1
        left=0
        right=len(nums)-1
        while left<right:
            mid=(left+right)//2
            if nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
            elif nums[mid]==target:
                right-=1
        return left if nums[left]==target else -1

发表于 2022-01-20 23:38:28 回复(0)
Python 3
Melodychen头像 Melodychen
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        total_len=len(nums)
        max_index=total_len-1
        min_index=0
        while max_index >= min_index:
            index=(max_index+min_index)//2
            if nums[index]>target:
                max_index=index-1
            elif nums[index]<target:
                min_index=index+1
            elif nums[index] == target:
                if max_index==min_index:
                    return index
                else:
                    max_index=index
        return -1
发表于 2022-01-07 21:15:09 回复(0)
Python 3
henryboy233头像 henryboy233 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 如果目标值存在返回下标，否则返回 -1
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # write code here
        front,end = 0,len(nums) - 1
        while front <= end:
            temp = (front + end) // 2
            if nums[temp] == target:
                temp1 = temp
                while temp1 >= 0 and nums[temp1] == target:
                    temp1 -= 1
                return temp1+ 1
            elif nums[temp] > target:
                end = temp - 1
            else:
                front = temp + 1
        else:
            return -1

        

发表于 2021-12-10 13:02:11 回复(0)
Python 3
JSFaner头像 JSFaner 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        left,right = 0,len(nums)-1
        while left<=right:
            mid = (left+right)//2
            if nums[mid]<target: left = mid +1
            elif nums[mid]>target: right = mid -1
            elif nums[mid]==target: right = mid -1
        if left < len(nums) and nums[left] == target:
            return left
        else:
            return -1

发表于 2021-11-13 12:36:30 回复(0)
Python 3
郁存幻头像 郁存幻 
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 如果目标值存在返回下标，否则返回 -1
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def search(self , nums , target ):
        # write code here
        for i,v in enumerate(nums):
            if target==v:                
                return i                           
        return -1

发表于 2021-10-24 17:37:06 回复(0)
Python 3
传说中的2东东幺头像 传说中的2东东幺 
class Solution:
    def search(self , nums , target ):
        # write code here
        n = len(nums)
        if not n:return -1
        left,right = 0,n-1
        while left <= right:
            mid = left+(right-left)//2
            if nums[mid] < target:
                left = mid+1
            elif nums[mid] >target:
                right = mid-1
            else:
                left = mid
                while left > 0:
                    if nums[left-1] != target:
                        break
                    left -= 1
                return left
        return -1

发表于 2021-10-22 11:25:32 回复(0)
Python 3
昊天明月头像 昊天明月
class Solution:
    def search(self , nums , target ):
        i : int = 0
        j : int = len(nums)-1
        if j<0:
            return -1
        while i<j:
            mid = i + (j-i)//2
            if nums[mid] >= target:
                j = mid
            else:
                i = mid + 1
        if nums[i] == target:
            return i
        return -1
发表于 2021-09-11 10:32:29 回复(0)
Python 3
牛客38477449号头像 牛客38477449号 
class Solution:
    def search(self , nums , target ):
        # write code here
        res = -1
        low, high = 0, len(nums)-1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] == target:
                res = mid
                high = mid - 1
            elif nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        return res

发表于 2021-09-08 16:37:14 回复(0)
Python 3
牛客919617007号头像 牛客919617007号
class Solution:
    def search(self , nums , target ):
        if target in nums:
            for i in range(len(nums)):
                if nums[i] == target:
                    return i
        else:
            return -1
发表于 2021-08-22 15:44:25 回复(0)
Python 3
牛客35961088号头像 牛客35961088号 
class Solution:
    def search(self , nums , target ):
        # write code here
        if not nums: return -1
        start = 0
        end = len(nums)
        while start <= end:
            mid = (end+start) // 2
            if nums[mid] == target:
                if mid>0 and nums[mid-1] == target:
                    end = mid - 1
                else:
                    return mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return -1

发表于 2021-07-29 17:22:59 回复(0)
Python 3
火炜头像 火炜 
class Solution:
    def search(self , nums , target ):
        if len(nums) == 0:
            return -1
        left = 0
        right = len(nums)-1
        t = int((left+right)/2)
        while left <= right:
            if nums[t] == target:
                while nums[t] == target and t>=0:
                    t = t-1
                return t+1
            elif target < nums[t]:
                right = t-1
            elif target > nums[t]:
                left = t+1
            t = int((left+right)/2)
        return -1

发表于 2021-07-22 14:09:19 回复(0)
Python 3
dingx92头像 dingx92 
class Solution:
    def search(self , nums , target ):
        # write code here
        n = len(nums)
        if n==0:
            return -1
        left, right = 0, n-1
        while left<right:
            mid = left + (right-left)//2
            if nums[mid]==target:
                while mid-1>=0 and nums[mid-1]==nums[mid]:
                    mid-=1
                return mid
            elif nums[mid]<target:
                left=mid+1
            else:
                right = mid
        
        if nums[left]==target:
            while left-1>=0 and nums[left-1]==nums[left]:
                left-=1
            return left
        else:
            return -1

发表于 2021-07-14 18:19:16 回复(0)
提交观点

问题信息

二分
难度：
17条回答 5390浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号